(1) Field of the Invention
This invention relates to a data relay apparatus for relaying a packet transmitted, a content addressable/associative memory device used in such a data relay apparatus, and a content addressable/associative memory device use information search method for searching for information regarding a packet by using such a content addressable/associative memory device and, more particularly, to a data relay apparatus, a content addressable/associative memory device, and a content addressable/associative memory device use information search method for improving efficiency in information search.
(2) Description of the Related Art
In devices (data relay apparatus), such as routers and switches, which connect networks, a routing process is performed on the basis of the destinations of packets sent over the networks. Such a routing process may be performed by software with a general-purpose computer or may be performed by dedicated hardware.
If a routing process must be performed at high speed, usually dedicated hardware will be used for packet routing. In this case, each data relay apparatus includes a processor (network processor) dedicated to routing.
Such a network processor refers to various pieces of information, such as an internet protocol (IP) address, regarding a packet inputted and determines a physical port to which it should be outputted. Usually network processors include a memory for storing the IP addresses of terminal units connected to their physical ports. When a packet is transmitted, the contents of the memory are referred to. By doing so, a physical port to which the packet should be outputted can be specified.
As stated above, routing always involves memory access in a data relay apparatus. Accordingly, to perform routing at high speed, it is necessary to improve efficiency in memory access. For example, a command access circuit (or memory control circuit) for buffering a command is located between a central processing unit (CPU) and a memory as a technique for improving efficiency in access from the CPU to the memory (see, for example, Japanese Patent Unexamined Publication No. 8-87441 or No. 2000-99394).
In addition, a special memory referred to as a content addressable/associative memory (CAM) device is used especially for high-speed large-capacity routing. A routing circuit using a CAM device is also referred to as a network search engine.
A CAM device stores information, such as IP addresses. When information, such as an IP address, is inputted, the memory address of a storage area where the information is stored is outputted. CAM devices are used not only in data relay apparatus but also in various systems as high-speed memories (see Japanese Patent Unexamined Publication No. 2000-231785, paragraph [0023]).
By the way, there are cases where a network processor accesses a memory more than one time to search for a route for one packet. For example, IP addresses (source address (SA) and destination address (DA)) and port numbers (source port number and destination port number) used in, for example, Transmission Control Protocol (TCP)/User Datagram Protocol (UDP) are extracted from a packet and an IP address search and a port number search are made. That is to say, a search is made twice.
A route search process involving accessing a CAM device more than one time will now be described.
FIG. 17 shows a conventional route search process involving accessing a CAM device more than one time. As shown in FIG. 17, a data relay apparatus includes a network processor 911, a CAM device 912, and a context random access memory (RAM) 913. An IP address storage area and a port number storage area are included in a storage area in the CAM device 912. In this example, an IP address search and a port number search are made to transmit one packet. That is to say, a search is made twice.
[Step S101] When packet information is inputted to the data relay apparatus, the network processor 911 sends a search key 921, a mask setting command 922, and a search command 923 to the CAM device 912. The search key 921 is an IP address. The mask setting command 922 is a command for designating the process of masking an area in the CAM device 912 other than the IP address storage area (process of excluding an area in the CAM device 912 other than the IP address storage area from an area to be searched).
The CAM device 912 masks the area specified by the mask setting command 922. The masked area is excluded from an area to be searched. The CAM device 912 searches for data which matches the search key 921, and outputs the memory address of an area where data is stored. The memory address outputted is inputted to the context RAM 913 as a read memory address. Then data 924 is outputted from an area in the context RAM 913 corresponding to the memory address inputted to the network processor 911. This search process is performed in the Layer 3 (network layer).
[Step S102] Next, the network processor 911 sends a search key 931, a mask setting command 932, and a search command 933 to the CAM device 912. The search key 931 is a port number indicative of a destination application to which the packet is transmitted. The mask setting command 932 is a command for designating the process of masking an area in the CAM device 912 other than the port number storage area.
The CAM device 912 masks the area specified by the mask setting command 932. The CAM device 912 searches for data which matches the search key 931, and outputs the memory address of an area where the data is stored. The memory address outputted is inputted to the context RAM 913 as a read memory address. Then data 934 is outputted from an area in the context RAM 913 corresponding to the memory address inputted to the network processor 911. This search process is performed in the Layer 4 (transport layer).
To provide a service, such as quality of service (QoS), it is necessary to identify a flow not only by IP addresses (SA and DA) in the Layer 3 but also by information in the Layer 4. Accordingly, a search is made twice.
However, if a CAM device is accessed more than one time to transmit one packet, a mask setting command and a search command are issued each time a search is made. This increases the number of times a CAM device is accessed and degrades the performance of a network processor. Therefore, to perform processes, such as packet routing, at higher speeds, it is hoped that commands will be transmitted more efficiently at the time of access to a CAM device.